package mid;

import java.util.LinkedList;

/**
 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
 1. 0<=pushV.length == popV.length <=1000
 2. -1000<=pushV[i]<=1000
 3. pushV 的所有数字均不相同
 *
 *
 * @author WangZhiJian
 * @since 2022/1/20
 */
public class 栈的压入弹出序列 {

    /**
     * 运行时间：33ms
     * 超过5.11% 用Java提交的代码
     * 占用内存：10420KB
     * 超过3.19%用Java提交的代码
     * @param pushA
     * @param popA
     * @return
     */
    public static boolean IsPopOrder(int [] pushA,int [] popA) {
        if(popA == null || popA.length == 0)
            return false;

        LinkedList<Integer> stack = new LinkedList<>();
        int i = 0;
        int popLen = popA.length;
        int pushLen = pushA.length;
        for (int k = 0; k < popLen; k++) {
            // 当栈为空,且不是最后一个元素,并且栈顶不是我们期望的元素,我们一直往里面push
            while ( i < pushLen && (stack.isEmpty() || stack.peek() != popA[k]) ){
                stack.push(pushA[i]);
                i++;
            }
            // 栈顶元素不为期望值返回false
            if( stack.peek() != popA[k] )
                return false;
            stack.pop();
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(IsPopOrder(new int[]{1, 2, 3, 4, 5}, new int[]{4,3,5,1,2}));
    }
}
